Incremental Bridge-Connectivity

#Graphs

Operations

$$n$$頂点の無向グラフを扱う

空間計算量$$\Theta(n)$$

$$\mathtt{new}(n)$$

$$n$$頂点の辺を持たないグラフを作成する.

時間計算量$$\Theta(n \log n) \ \rm amortized$$

$$\mathtt{insert\_edge}(u, v)$$

無向辺$$(u, v)$$を追加する.

時間計算量$$\Theta(1) \ \rm amortized$$

$$\mathtt{bridge\_connected}(u, v)$$

$$u$$と$$v$$が二辺連結か判定する.

時間計算量$$\Theta(1) \ \rm amortized$$

Summary

連結成分と二辺連結成分のそれぞれをUnion Findで管理する.

また, 二辺連結成分を圧縮して得られる森を, 各頂点が親を保持する形で管理する.

$$\mathtt{insert\_edge}(u, v)$$

$$u$$と$$v$$が非連結の場合

$$u$$の属する木が$$v$$のそれより小さいとする.

適宜辺を反転して$$u$$を根にし, $$u$$の親を$$v$$にすることで木を連結する.

$$u$$と$$v$$が連結の場合

$$uv$$パス上の頂点を全て同じ二辺連結成分としてまとめる.

$$u$$と$$v$$から交互に親を辿ることにより, $$uv$$パス長のオーダーでパス上の頂点を列挙する.

References

Maintaining bridge-connected and biconnected components on-line

Notes

内部で二辺連結成分のUnion Findを管理しているため, 連結性判定の他にも代表元の取得などが可能.

ある辺が橋であるかどうかの判定もできる

$$u$$と$$v$$が非連結の場合は, 辺$$(u, v)$$に橋フラグを立てる

$$u$$と$$v$$が連結の場合, $$uv$$パス上の辺の橋フラグを取り除く

よりオーダーが高速なアルゴリズムも同論文で示されている.

Implementations

C++: noshi91/incremental_bridge_connectivity

C++: niuez/incremental_bridge_connectivity